package problems.daily;

/**
 * 1140. 石子游戏 II
 * <p>https://leetcode.cn/problems/stone-game-ii/</p>
 *
 * @author habitplus
 * @since 2023/2/22 11:15
 */
public class DT1140 {

    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int sum = 0;
        int[][] dp = new int[n][n + 1];
        int tmin;

        for (int i = n - 1; i >= 0; --i) {
            sum += piles[i];

            for (int m = 1; m <= n; ++m) {
                if (i + 2 * m >= n) {
                    // 能一次性拿完
                    dp[i][m] = sum;
                } else {
                    // 不能，则尽量让Bob拿到最少
                    tmin = Integer.MAX_VALUE;
                    for (int x = 1; x <= m * 2; ++x) {
                        tmin = Math.min(tmin, dp[i + x][Math.max(x, m)]);
                    }
                    dp[i][m] = sum - tmin;
                }
            }
        }

        return dp[0][1];
    }

    public static void main(String[] args) {
        System.out.println(new DT1140().stoneGameII(new int[]{2, 7, 9, 4, 4}));
    }
}
